//package homework;
//
//class Node {
//    public int val;
//    public Node next;
//
//    public Node(int val) {
//        this.val = val;
//    }
//}
//
//public class MyLinkedList {
//    private Node head = null;
//
//    //头插法
//    public void addFirst(int data) {
//        Node node = new Node(data);
//
//        if (head == null) {
//            head = node;
//            return;
//        }
//
//        node.next = head;
//        head = node;
//    }
//
//    //尾插法
//    public void addLast(int data) {
//        Node node = new Node(data);
//
//        if (head == null) {
//            head = node;
//            return;
//        }
//
//        Node cur = head;
//        while (cur.next != null) {
//            cur = cur.next;
//        }
//
//        cur.next = node;
//    }
//
//    //打印
//    public void display() {
//        for (Node cur = head; cur != null; cur = cur.next) {
//            System.out.print(cur.val + " ");
//        }
//        System.out.println();
//    }
//
//    //单链表长度
//    public int getSize() {
//        int size = 0;
//        for (Node cur = head; cur != null; cur = cur.next) {
//            size++;
//        }
//        return size;
//    }
//
//    //插入
//    public boolean addIndex(int index, int data) {
//        int size = getSize();
//        if (index < 0 || index > size) {
//            return false;
//        }
//        if (index == 0) {
//            addFirst(data);
//            return true;
//        }
//        if (index == size) {
//            addLast(data);
//            return true;
//        }
//
//        Node node = new Node(data);
//        Node pre = getPos(index - 1);
//        node.next = pre.next;
//        pre.next = node;
//        return true;
//
//    }
//
//    //给出下标得到对应下标的结点
//    public Node getPos(int index) {
//        Node cur = head;
//        for (int i = 0; i < index; i++) {
//            cur = cur.next;
//        }
//        return cur;
//    }
//
//    //查找链表是否包含该元素
//    public boolean contains(int toFind) {
//        for (Node cur = head; cur != null; cur = cur.next) {
//            return true;
//        }
//        return false;
//    }
//
//    //找到toRemove的前一个结点
//    public Node searchPrev(int toRemove) {
//        for (Node cur = head; cur != null && cur.next != null; cur = cur.next) {
//            if(cur.next.val == toRemove){
//                return cur;
//            }
//        }
//        return null;
//    }
//
//    //删除结点
//    public void remove(int toRemove){
//        if(head.val == toRemove){
//            head = head.next;
//            return;
//        }
//        Node pre = searchPrev(toRemove);
//        pre.next = pre.next.next;
//    }
//
//    //删除所有出现关键字为key结点
//    public void removeAllKey(int key){
//        Node cur = head;
//        if(head.val == key){
//            head = head.next;
//        }
//        while (cur != null){
//            if(cur.next.val == key){
//                Node pre = searchPrev(key);
//                pre.next = pre.next.next;
//            }
//            cur = cur.next;
//        }
//    }
//
//    //删除所有结点
//    public void clear(){
//        Node cur = head;
//        while (cur != cur){
//            cur.val = 0;
//            cur = cur.next;
//        }
//    }
//
//    public static void main(String[] args) {
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addFirst(12);
//        myLinkedList.addFirst(13);
//        myLinkedList.addFirst(14);
//        myLinkedList.display();
//        myLinkedList.addLast(1);
//        myLinkedList.addLast(2);
//        myLinkedList.addLast(3);
//        myLinkedList.addLast(3);
//        myLinkedList.display();
////        myLinkedList.searchPrev(3);
//        myLinkedList.removeAllKey(3);
//        myLinkedList.display();
////        myLinkedList.clear();
//    }
//}
